home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / lzpipe / trees.c < prev    next >
Text File  |  1994-03-13  |  39KB  |  1,051 lines
  1. /*
  2.  The following sorce code is derived from Info-Zip 'zip' 2.01
  3.  distribution copyrighted by Mark Adler, Richard B. Wales,
  4.  Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  5. */
  6.  
  7. /*
  8.  *  trees.c by Jean-loup Gailly
  9.  *
  10.  *  This is a new version of im_ctree.c originally written by Richard B. Wales
  11.  *  for the defunct implosion method.
  12.  *
  13.  *  PURPOSE
  14.  *
  15.  *      Encode various sets of source values using variable-length
  16.  *      binary code trees.
  17.  *
  18.  *  DISCUSSION
  19.  *
  20.  *      The PKZIP "deflation" process uses several Huffman trees. The more
  21.  *      common source values are represented by shorter bit sequences.
  22.  *
  23.  *      Each code tree is stored in the ZIP file in a compressed form
  24.  *      which is itself a Huffman encoding of the lengths of
  25.  *      all the code strings (in ascending order by source values).
  26.  *      The actual code strings are reconstructed from the lengths in
  27.  *      the UNZIP process, as described in the "application note"
  28.  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  29.  *
  30.  *  REFERENCES
  31.  *
  32.  *      Lynch, Thomas J.
  33.  *          Data Compression:  Techniques and Applications, pp. 53-55.
  34.  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
  35.  *
  36.  *      Storer, James A.
  37.  *          Data Compression:  Methods and Theory, pp. 49-50.
  38.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  39.  *
  40.  *      Sedgewick, R.
  41.  *          Algorithms, p290.
  42.  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  43.  *
  44.  *  INTERFACE
  45.  *
  46.  *      int ct_init (void)
  47.  *          Allocate the match buffer and initialize the various tables.
  48.  *
  49.  *      int ct_tally(int dist, int lc);
  50.  *          Save the match info and tally the frequency counts.
  51.  *          Return true if the current block must be flushed.
  52.  *
  53.  *      long flush_block (char *buf, ulg stored_len, int eof)
  54.  *          Determine the best encoding for the current block: dynamic trees,
  55.  *          static trees or store, and output the encoded block to the zip
  56.  *          file. Returns the total compressed length for the file so far.
  57.  */
  58.  
  59. #include "modern.h"
  60. #include "zalloc.h"
  61. #include "zipdefs.h"
  62. #include "zipguts.h"
  63. #include "lzpipe.h"
  64.  
  65. #define MAX_BITS 15
  66. /* All codes must not exceed MAX_BITS bits */
  67.  
  68. #define MAX_BL_BITS 7
  69. /* Bit length codes must not exceed MAX_BL_BITS bits */
  70.  
  71. #define LENGTH_CODES 29
  72. /* number of length codes, not counting the special END_BLOCK code */
  73.  
  74. #define LITERALS  256
  75. /* number of literal bytes 0..255 */
  76.  
  77. #define END_BLOCK 256
  78. /* end of block literal code */
  79.  
  80. #define L_CODES (LITERALS+1+LENGTH_CODES)
  81. /* number of Literal or Length codes, including the END_BLOCK code */
  82.  
  83. #define D_CODES   30
  84. /* number of distance codes */
  85.  
  86. #define BL_CODES  19
  87. /* number of codes used to transfer the bit lengths */
  88.  
  89. static int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
  90.    = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
  91.  
  92. static int near extra_dbits[D_CODES] /* extra bits for each distance code */
  93.    = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
  94.  
  95. static int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
  96.    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
  97.  
  98. #define STORED_BLOCK 0
  99. #define STATIC_TREES 1
  100. #define DYN_TREES    2
  101. /* The three kinds of block type */
  102.  
  103. #ifndef LIT_BUFSIZE
  104. #  ifdef SMALL_MEM
  105. #    define LIT_BUFSIZE  0x2000
  106. #  else
  107. #  ifdef MEDIUM_MEM
  108. #    define LIT_BUFSIZE  0x4000
  109. #  else
  110. #    define LIT_BUFSIZE  0x8000
  111. #  endif
  112. #  endif
  113. #endif
  114. #define DIST_BUFSIZE  LIT_BUFSIZE
  115. /* Sizes of match buffers for literals/lengths and distances.  There are
  116.  * 4 reasons for limiting LIT_BUFSIZE to 64K:
  117.  *   - frequencies can be kept in 16 bit counters
  118.  *   - if compression is not successful for the first block, all input data is
  119.  *     still in the window so we can still emit a stored block even when input
  120.  *     comes from standard input.  (This can also be done for all blocks if
  121.  *     LIT_BUFSIZE is not greater than 32K.)
  122.  *   - if compression is not successful for a file smaller than 64K, we can
  123.  *     even emit a stored file instead of a stored block (saving 5 bytes).
  124.  *   - creating new Huffman trees less frequently may not provide fast
  125.  *     adaptation to changes in the input data statistics. (Take for
  126.  *     example a binary file with poorly compressible code followed by
  127.  *     a highly compressible string table.) Smaller buffer sizes give
  128.  *     fast adaptation but have of course the overhead of transmitting trees
  129.  *     more frequently.
  130.  *   - I can't count above 4
  131.  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  132.  * memory at the expense of compression). Some optimizations would be possible
  133.  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  134.  */
  135.  
  136. #define REP_3_6      16
  137. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  138.  
  139. #define REPZ_3_10    17
  140. /* repeat a zero length 3-10 times  (3 bits of repeat count) */
  141.  
  142. #define REPZ_11_138  18
  143. /* repeat a zero length 11-138 times  (7 bits of repeat count) */
  144.  
  145. /* Data structure describing a single value and its code string. */
  146. typedef struct ct_data {
  147.     union {
  148.         ush  freq;       /* frequency count */
  149.         ush  code;       /* bit string */
  150.     } fc;
  151.     union {
  152.         ush  dad;        /* father node in Huffman tree */
  153.         ush  len;        /* length of bit string */
  154.     } dl;
  155. } ct_data;
  156.  
  157. #define Freq fc.freq
  158. #define Code fc.code
  159. #define Dad  dl.dad
  160. #define Len  dl.len
  161.  
  162. #define HEAP_SIZE (2*L_CODES+1)
  163. /* maximum heap size */
  164.  
  165. static ct_data near dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  166. static ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */
  167.  
  168. static ct_data near static_ltree[L_CODES+2];
  169. /* The static literal tree. Since the bit lengths are imposed, there is no
  170.  * need for the L_CODES extra codes used during heap construction. However
  171.  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  172.  * below).
  173.  */
  174.  
  175. static ct_data near static_dtree[D_CODES];
  176. /* The static distance tree. (Actually a trivial tree since all codes use
  177.  * 5 bits.)
  178.  */
  179.  
  180. static ct_data near bl_tree[2*BL_CODES+1];
  181. /* Huffman tree for the bit lengths */
  182.  
  183. typedef struct tree_desc {
  184.     ct_data near *dyn_tree;      /* the dynamic tree */
  185.     ct_data near *static_tree;   /* corresponding static tree or NULL */
  186.     int     near *extra_bits;    /* extra bits for each code or NULL */
  187.     int     extra_base;          /* base index for extra_bits */
  188.     int     elems;               /* max number of elements in the tree */
  189.     int     max_length;          /* max bit length for the codes */
  190.     int     max_code;            /* largest code with non zero frequency */
  191. } tree_desc;
  192.  
  193. static tree_desc near l_desc =
  194. {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};
  195.  
  196. static tree_desc near d_desc =
  197. {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};
  198.  
  199. static tree_desc near bl_desc =
  200. {bl_tree, (ct_data near *)0, extra_blbits, 0,     BL_CODES, MAX_BL_BITS, 0};
  201.  
  202. static ush near bl_count[MAX_BITS+1];
  203. /* number of codes at each bit length for an optimal tree */
  204.  
  205. static uch near bl_order[BL_CODES]
  206.    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
  207. /* The lengths of the bit length codes are sent in order of decreasing
  208.  * probability, to avoid transmitting the lengths for unused bit length codes.
  209.  */
  210.  
  211. static int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
  212. static int heap_len;               /* number of elements in the heap */
  213. static int heap_max;               /* element of largest frequency */
  214. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  215.  * The same heap array is used to build all trees.
  216.  */
  217.  
  218. static uch near depth[2*L_CODES+1];
  219. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  220.  
  221. static uch length_code[MAX_MATCH-MIN_MATCH+1];
  222. /* length code for each normalized match length (0 == MIN_MATCH) */
  223.  
  224. static uch dist_code[512];
  225. /* dis